﻿// Pushing Boxes POJ - 1475.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://vjudge.net/problem/POJ-1475#author=GPT_zh

想象一下，你站在一个由方形单元格组成的二维迷宫内，这些单元格可能被填满了岩石，也可能是空的。你可以向北、南、东或西移动一步。这些移动被称为步行。
其中一个空单元格包含一个箱子，可以通过站在箱子旁边然后朝着箱子的方向移动，将箱子移动到相邻的空单元格中。这样的移动被称为推动。箱子不能以除推动以外的任何方式移动，这意味着如果你把它推到角落里，你就再也无法把它推出来了。

其中一个空单元格被标记为目标单元格。你的任务是通过一系列步行和推动，将箱子带到目标单元格。由于箱子非常沉，你希望最小化推动的次数。你能编写一个程序来找出最佳的移动序列吗？

输入
输入包含多个迷宫的描述。每个迷宫描述以包含两个整数 r 和 c（均小于或等于 20）的一行开始，表示迷宫的行数和列数。

接下来是 r 行，每行包含 c 个字符。每个字符描述迷宫的一个单元格。用 `#' 表示充满岩石的单元格，用 `.' 表示空单元格。你的起始位置用 `S' 表示，箱子的起始位置用 `B' 表示，目标单元格用 `T' 表示。

输入以 r 和 c 均为零的两个数字结束。
输出
对于输入中的每个迷宫，首先打印迷宫的编号，如示例输出所示。然后，如果无法将箱子带到目标单元格，则打印“Impossible.”。

否则，输出一个最小化推动次数的序列。如果存在多个这样的序列，请选择最小化总移动次数（步行和推动）的序列。如果仍然存在多个这样的序列，则任何一个都可以接受。

将序列输出为字符 N、S、E、W、n、s、e 和 w 的字符串，其中大写字母表示推动，小写字母表示步行，不同的字母表示北、南、东和西的方向。

在每个测试用例后输出一个空行。

1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

*/
int main()
{
    std::cout << "Hello World!\n";
}
 